package com.mrzhou.study.struct.stack;

import com.mrzhou.core.tool.utils.Func;
import com.mrzhou.study.struct.queue.ArrayQueue;
import com.mrzhou.study.struct.support.CalculateUtil;
import com.mrzhou.study.struct.support.CharStack;
import com.mrzhou.study.struct.support.NumStack;

/**
 * 使用栈计算字符算式
 *  三种表达式: 前缀(波兰)表达式、中缀表达式、后缀(逆波兰)表达式
 *  前缀表达式: 又称波兰表达式, 前缀表达式的运算符位于操作数之前
 *      示例: "(3+4)×5-6" 对应的前缀表达式就是 "- × + 3 4 5 6"
 *  中缀表达式: 数学中使用的表达式
 *      示例: "(3+4)×5-6"就是中缀表达式
 *  后缀表达式: 又称逆波兰表达式, 运算符位于操作数之后
 *      示例: "(3+4)×5-6" 对应的后缀表达式就是 "3 4 + 5 × 6 –"
 */
public class Calculate {

    /**
     * 计算前缀表达式, 扫描字符时需要从右向左扫描
     */
    public int prefix(String prefix) {
        NumStack numStack = new NumStack(50);
        CharStack charStack = new CharStack(50);
        char[] chars = prefix.toCharArray();

        String num = "";
        for(int i = chars.length -1 ; i >= 0; i--) { // 从右向左扫描字符
            char c = chars[i];
            if(numStack.isDigit(c) && numStack.isDigit(chars[i - 1])) { // 处理多位整数
                num += c;
            } else if(charStack.isOper(c)) {
                int var1 = numStack.pop(), var2 = numStack.pop();
                numStack.push(CalculateUtil.choose(var1, var2, c));
            } else if(numStack.isDigit(c)) {
                numStack.push(Integer.parseInt(reversal(num + c)));
                num = "";
            }
        }
        return numStack.pop();
    }

    /**
     * 中缀表达式计算
     * @param infix
     * @return
     */
    public int infix(String infix) {
        NumStack numStack = new NumStack(50);
        CharStack charStack = new CharStack(50);
        char chars[] = infix.toCharArray();

        String num = "";
        for(int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if(i != chars.length -1 && numStack.isDigit(c) && numStack.isDigit(chars[i+1])) {
                num += c;
            } else if(charStack.isLegalChar(c)) {
                if(c == ')') { // 当前符号为左括号时, 处理括号中的运算符
                    char peek = charStack.pop(); // 现将符号栈的栈顶元素取出
                    while(peek != '(') { // 扫描到栈中第一个右括号的位置结束
                        int var1 = numStack.pop(), var2 = numStack.pop();
                        numStack.push(CalculateUtil.choose(var2, var1, peek)); // 弹出当前符号栈栈顶元素, 进行计算
                        peek = charStack.pop(); // 再次取出下一个栈顶元素
                    }
                    continue; // 计算完成后立即进入下次循环
                }
                // 判断即将插入的和当前栈顶操作符的优先级 如果即将插入的运算符优先级小于等于peek的优先级
                char peek = charStack.peek(); // 获取当前符号栈栈顶的操作符
                while(charStack.isOpers(c, peek) && charStack.priority(c) <= charStack.priority(peek)) {
                    int var1 = numStack.pop(),  var2 = numStack.pop();
                    numStack.push(CalculateUtil.choose(var2, var1, charStack.pop())); // 将当前符号栈栈顶数据pop出计算, 因为之前只是查看当前的栈顶数据
                    peek = charStack.peek(); // 再次获取栈顶数据
                }
                charStack.push(c);
            } else if (numStack.isDigit(c)) {
                numStack.push(Integer.parseInt(num + c));
                num = "";
            }
        }

        // 将两个栈中的数据汇总
        while(!charStack.isEmpty()) {
            int var1 = numStack.pop(), var2 = numStack.pop();
            numStack.push(CalculateUtil.choose(var2, var1, charStack.pop()));
        }

        return numStack.pop();
    }

    /**
     * 计算后缀表达式, 由右至左扫描字符算式
     */
    public int suffix(String suffix) {
        NumStack numStack = new NumStack(50);
        CharStack charStack = new CharStack(50);
        char[] chars = suffix.toCharArray();
        String num = "";
        for(int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if(numStack.isDigit(c) && i != chars.length -1  && numStack.isDigit(chars[i+1])) {
                num += c;
            } else if (charStack.isOper(c)) {
                int var1 = numStack.pop(), var2 = numStack.pop();
                numStack.push(CalculateUtil.choose(var2, var1, c)); // 计算结果比较结果压入数字栈
            } else if (numStack.isDigit(c)) {
                numStack.push(Integer.parseInt(num + c));
                num = "";
            }
        }
        return numStack.pop();
    }

    public static void main(String[] args) {
        Calculate calculate = new Calculate();
        String prefix = "- * + 3 4 5 6 ";
        int result = calculate.prefix(prefix);
        int i = (3 + 4) * 5 - 6; // 前缀表达式: - * + 3 4 5 6  后缀表达式: 3 4 + 5 * 6 -
        System.out.printf("前缀算式 %s = %d\t i = %d\n", prefix, result, i);

        String infix = "(5*((7+ 7*4 - 4 +8*9)/(3+4))) + 1 * 8";
        i = (5*((7+ 7*4 - 4 +8*9)/(3+4))) + 1 * 8;
        System.out.printf("中缀算式 %s = %d\t i = %d\n", infix, calculate.infix(infix), i);

        String suffix = calculate.infixToSuffix(infix);
//        System.out.printf("中缀转后缀: \n中缀: %s\n后缀: %s\n", infix, suffix);
        System.out.printf("后缀算式 %s = %d\t i = %d\n", suffix, calculate.suffix(suffix), i);
    }


    /**'
     *  将中缀表达式转换成后缀表达式
     * @param infix 中缀算式表达式
     */
    public String infixToSuffix(String infix) {
        CharStack operStack = new CharStack(200); // 操作符号栈
        ArrayQueue<String> result = new ArrayQueue<>(1024); // 因队列的先进先出的特性,这里使用队列保存结果
//        CharStack charStack = new CharStack(1024); // 后缀表达式的结果栈
        char chars[] = infix.toCharArray();
        String num = "";
        for(int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if(i != chars.length - 1 && CalculateUtil.isDigit(c) && CalculateUtil.isDigit(chars[i+1])) { // 只要是数字就直接压入结果栈
                num += c;
            } else if (CalculateUtil.isLegalOper(c)){
                if(c == ')') {
                    char cur = operStack.pop();
                    while(cur != '(') {
                        result.add(Func.toStr(cur)); // 压入
                        cur = operStack.pop();// 再次弹出操作符栈的栈顶元素
                    }
                    continue; // 因为是左括号, 直接丢弃
                }
                char cur = operStack.peek();
                // 如果即将插入的运算符小于或等于当前操作符栈栈顶的操作符优先级, 则将当前操作符栈顶的数据压入结果栈, 然后咱把
                while(CalculateUtil.isOpers(c, cur) && CalculateUtil.priority(c) <= CalculateUtil.priority(cur)) {
                    result.add(Func.toStr(operStack.pop())); // 先弹出操作符栈的栈顶元素, 压入到结果栈中;
                    cur = operStack.peek();
                }
                operStack.push(c);
            } else if(CalculateUtil.isDigit(c)) {
                result.add(num + c);
                num = "";
            }
        }

        // 将操作符栈中剩余的数据直接压入结果栈中
        while(!operStack.isEmpty()) {
            result.add(Func.toStr(operStack.pop()));
        }

        // 将队列中的数据按后缀表达式标椎转换成string
        StringBuffer sb  = new StringBuffer();
        while(!result.isEmpty()) {
            sb.append(result.poll()).append(" ");
        }
        return sb.toString().trim();
    }

    /**
     * 将字符逆序输出
     */
    private String reversal(String origin) {
        char chars[] = origin.toCharArray();
        StringBuffer sb = new StringBuffer("");
        for(int i = chars.length - 1; i >= 0; i--) {
            sb.append(chars[i]);
        }
        return sb.toString();
    }

}
